package 困难.哈希表;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
 * 实现 FreqStack 类:
 * FreqStack() 构造一个空的堆栈。
 * void push(int val) 将一个整数 val 压入栈顶。
 * int pop() 删除并返回堆栈中出现频率最高的元素。
 * 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-frequency-stack
 */
public class 最大频率栈_895 {

    public static void main(String[] args) {

        FreqStack freqStack = new FreqStack();
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);

        freqStack.pop();
        freqStack.pop();

    }

    /**
     * 思路：
     * 为每个频率的数字分别维护一个栈
     * 方法：
     * 一个哈希表记录，每个 val 出现的次数
     * 一个哈希表记录，每个 val 出现的次数对应的 栈
     * 需要维护最大次数，每次取数需要再最大次数的栈里面去取
     */
    static class FreqStack {

        private int maxCount;

        private Map<Integer, Integer> mapCount;

        private Map<Integer, Deque<Integer>> mapStack;

        public FreqStack() {
            mapCount = new HashMap<>();
            mapStack = new HashMap<>();
        }

        public void push(int val) {
            mapCount.put(val, mapCount.getOrDefault(val, 0) + 1);
            Integer curCount = mapCount.get(val);
            Deque<Integer> curStack = mapStack.get(curCount);
            if (curStack == null) {
                curStack = new ArrayDeque<>();
                mapStack.put(curCount, curStack);
            }

            curStack.addFirst(val);
            maxCount = Math.max(maxCount, curCount);
        }

        public int pop() {
            Deque<Integer> stack = mapStack.get(maxCount);
            Integer val = stack.pollFirst();
            if (stack.isEmpty()) {
                maxCount--;
            }
            mapCount.put(val, mapCount.get(val) - 1);
            return val;
        }
    }

}
